/*
  Insert Node at a given position in a linked list 
  The linked list will not be empty and position will always be valid
  First element in the linked list is at position 0
  Node is defined as 
  struct Node
  {
     int data;
     struct Node *next;
  }
*/
Node* InsertNth(Node *head, int data, int position)
{
    // Complete this method only
    // Do not write main function.
    if(position == 0) {
        Node *nh = new Node();
        nh->data = data;
        nh->next = head;
        return nh;
    } else {
        Node *n = head;
        for(int i = 1; i < position; i++)
            n = n->next;
        Node *pn = n->next;
        n->next = new Node();
        n->next->data = data;
        n->next->next = NULL;
        n->next->next = pn;
        return head;
    }
}